/* Implements queue abstract data type. */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

typedef struct queue_link_data_t *queue_link_t;

/* Define link*/
struct queue_link_data_t {
  queue_element_t e;
  queue_link_t next;
};

struct queue_data_t {
  queue_link_t head;
};

queue_t
queue_create()
{
  queue_t q = (queue_t)malloc(sizeof(struct queue_data_t));
  q->head = NULL;
  return q;
}

/* Private */
static queue_link_t
queue_new_element(queue_element_t e)
{
  queue_link_t qlt = (queue_link_t)malloc(sizeof(struct queue_link_data_t));
  qlt->e  = e;
  qlt->next = NULL;
  return qlt;
}


void
queue_append(queue_t q, queue_element_t e) 
{
  queue_link_t cur;
	
  assert(q != NULL);

  cur = q->head;

  /* when q is empty, we need to have it point the newly create link */
  if (cur==NULL){
    q->head = queue_new_element(e); 
    return;
  }
  
  while (cur->next) {
    cur = cur->next;
  }
  cur->next = queue_new_element(e);
}


boolean_t
queue_remove(queue_t q, queue_element_t *e) 
{
  queue_link_t oldHead;
	
  assert(q != NULL);
  if (queue_is_empty(q))
    return FALSE;

  *e = q->head->e;
  
  oldHead = q->head;
  q->head = q->head->next; 
  free(oldHead);
  return TRUE;
}


boolean_t
queue_is_empty(queue_t q)
{
  assert(q != NULL);
  return (q->head == NULL);
}


/* private */
static boolean_t
queue_count_one(queue_element_t e, queue_pfapply_closure_t cl)
{
  int *x = (int*)cl;
  *x = *x + 1;
  return TRUE;
}

int
queue_size(queue_t q)
{
  int sz = 0;
  queue_apply(q, queue_count_one, &sz);
  return sz;
}

boolean_t  
queue_apply(queue_t q, queue_pfapply_t pf, queue_pfapply_closure_t cl) 
{
  assert(q != NULL && pf != NULL);
  
  if (queue_is_empty(q))
    return FALSE;

  queue_link_t cur;
  for (cur = q->head; cur; cur = cur->next) {
    if (!pf(cur->e, cl))
      break; 
  }
  return TRUE;
}

void queue_reverse(queue_t q)
{
  assert(q!=NULL);
  
  // no need to do anything if size is smile than 2
  if (queue_size(q)<2)
    return;
  
  queue_link_t cur,prev,next;
  
  // initialize temporary pointers
  prev = NULL;
  cur = q->head;
  next = cur->next;

  while(next){
    cur->next = prev;
    prev = cur;
    cur = next;
    next = next->next;
  }
  // modify the pointer of old tail
  cur->next = prev;
  // have head of q to point to the oldtail
  q->head = cur;
} 

void queue_sort(queue_t q, queue_pfcompare_t pf){
  assert(q!=NULL && pf!=NULL);
  queue_link_t cur, one_of_the_rest;
  
  // start with the head
  cur = q->head;
  while(cur->next){
    //compare current with the rest of elements in the queue
    one_of_the_rest = cur->next;
    while(one_of_the_rest){
      if (pf(cur->e, one_of_the_rest->e)==1){
	//swap when e1 > e2
	queue_element_t temp;
	temp = cur->e;
	cur->e = one_of_the_rest->e;
	one_of_the_rest->e = temp;
      }
      one_of_the_rest = one_of_the_rest->next;
    }
    cur = cur->next;
  }
}
  
